package vip.zhenzicheng.algorithm.sort;

import vip.zhenzicheng.algorithm.util.ArrayUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * 基数排序
 *
 * @author zhenzicheng
 * @date 2022-06-09 20:42
 */
public class RadixSort {

  public static void main(String[] args) {
    int[] randomArray = ArrayUtils.getRandomArray(30, 50);
    radixSort(randomArray);
    ArrayUtils.printArray(randomArray);
  }

  public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }

    int max = arr[0];
    for (int i = 1; i < arr.length; i++) { // 找一个最大值
      max = Math.max(max, arr[i]);
    }

    int count = 0;
    while (max != 0) { // 判断最大值共有多少位
      max /= 10;
      count++;
    }

    List<List<Integer>> bucketList = new ArrayList<>();
    for (int i = 0; i < 10; i++) { // 每个桶放个位数[0,9]的数，所以是10个桶
      bucketList.add(new ArrayList<>());
    }

    int mod = 10, div = 1;
    // 按照从右往左的顺序，一次将每一位当做基数关键字，根据关键字将该数放入对应桶中完成一次排序
    for (int i = 0; i < count; i++, mod *= 10, div *= 10) { // 每进行完一次基数排序，将变量扩大
      for (int k : arr) { // 每次都遍历所有的元素
        int key = (k % mod) / div; // 获取第N个基准数，从右往左
        bucketList.get(key).add(k); // 将每一个元素放在其基准数关键字对应的桶里
      }

      int index = 0;
      for (List<Integer> everyBucketList : bucketList) {
        for (Integer num : everyBucketList) {
          arr[index++] = num;
        }
        everyBucketList.clear(); // 清空桶，准备下一次遍历
      }
    }
  }
}
